package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.Collections;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC497 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        TreeMap<Integer, int[]> candidateMap = new TreeMap<>();
        int sum = 0;
        Random random = new Random();

        public Solution(int[][] rects) {
            for (int[] rect : rects) {
                candidateMap.put(sum, rect);
                sum += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            }
        }

        public int[] pick() {
            int r = random.nextInt(sum);
            Integer floorKey = candidateMap.floorKey(r);
            int[] rect = candidateMap.get(floorKey);
            int w = rect[2] - rect[0] + 1;
            int x = (r - floorKey) % (w);
            int y = (r - floorKey) / (w);
            return new int[]{rect[0] + x, rect[1] + y};

//            int idx = (int) (Math.random() * sum);
//            int[] rect = candidateMap.get(candidateMap.ceilingKey(idx));
//            int row = (int) (Math.random() * (rect[2] - rect[0] + 1)), col = (int) (Math.random() * (rect[3] - rect[1] + 1));
//            return new int[]{rect[0] + row, rect[1] + col};
        }
    }

    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(rects);
     * int[] param_1 = obj.pick();
     */

    public void run() {
        int[][] arr = InputUtil.toDoubleIntegerArray("[[-2, -2, -1, -1], [1, 0, 3, 0]]");
        Solution solution = new Solution(arr);
        System.out.println(solution.pick());
    }

    public static void main(String[] args) throws Exception {
        LC497 an = new LC497();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
